#include <iostream>
using namespace std;

/**
 * @方法: KMP 算法
 * @时间复杂度: o(n+m)   n为主串长度
 * @空间复杂度: o(m)   m为模式串长度
 * @评价:
 */
void getNext(int next[], const string& pat) {
    next[0] = -1;
    int i = 0;
    int j = -1;
    while (i < pat.length() - 1) {
        if (j == -1 || pat[i] == pat[j]) {
            next[++i] = ++j;
        } else {
            j = next[j];
        }
    }
}

int strStr(string txt, string pat) {
    if (pat.length() == 0) return 0;
    // 获取 next 数组
    int next[pat.length()];
    getNext(next, pat);
    // 匹配
    int i = 0, j = 0;
    while (i < txt.length()) {
        if (j == -1 || txt[i] == pat[j]) {
            i++, j++;
            if(j == pat.length()) return i - pat.length();
        } else {
            j = next[j];
        }
    }
    return -1;
}

/**
 * @方法: Rabin-Karp 算法
 * @时间复杂度: o(m + n)
 * @空间复杂度: o()
 * @评价:  滚动哈希
 */



int main() {
    string txt = "hello";
    string pat = "ll";
    cout << strStr(txt, pat) << endl;
    return 0;
}